package com.tencent50.easy;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 合并两个有序数组
 * @date 2022/7/24 13:08
 */
public class Demo08 {
    public static void main(String[] args) {

        //int[] nums1 = {1,2,3,0,0,0}, nums2 = {2,5,6};
        //int  m=3,n=3;

        int[] nums1 = {2,0}, nums2 = {1};
        int  m=1,n=1;
        merge1(nums1,m,nums2,n);

    }
    //没做出来，因为一直考虑正序排序，倒着排序的话会简单点
    public static void merge(int[] nums1, int m, int[] nums2, int n) {

        int i=0;  //记录第一个数组扫描到的位置
        int j=0;  //记录第二个数组扫描到的位置

        while (i<nums1.length&&j<nums2.length){
            if(nums1[i]<=nums2[j]&&i==0){
                //第一个数组直接跳过，遍历第一个数组下个位置
                i++;
            }
            else if(nums1[i]<=nums2[j]&&(nums1[i]>nums1[i-1])){
                //第一个数组直接跳过，遍历第一个数组下个位置
                i++;
            }else {
                //第一个数组所有元素向后移动一位
                int k=nums1.length-1;
                while (k>=i+1){
                    nums1[k]=nums1[k-1];
                    k--;
                }
                nums1[i++]=nums2[j++];
            }
        }
    }


    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1,j=n-1;   //i和j分别表示，数组1和数组2分别需要排序的个数的索引下标最大值
        int len=m+n-1;//记录数组最后一个位置

        while (len>=0){
            //j<0 说明数组2需要参与排序的数据排完了 j和j指的是数组索引下标，而不是个数
            if(j<0){
                return;
            }
            //i索引下标最大值,小于0的话，证明数组一需要排序的排完了，倒叙排序的的话，拍的两个数较大的进入数组
            if(i>=0&&nums1[i]>nums2[j]){
                nums1[len--]=nums1[i--];
            }else {
                nums1[len--]=nums2[j--];
            }
        }
    }
}
